package com.melo;

import lombok.Data;

import java.util.Arrays;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 迪杰斯特拉算法: 公交图
 * @date 2025-06-09
 */
@Data
public class DijkstraBusGraph {

    /**
     * 顶点数组: 公交站台
     */
    private char[] busStationVertexArr;

    /**
     * 邻接矩阵: 公交路线
     */
    private int[][] busRouteMatrixArr;

    /**
     * 已经访问的顶点的集合
     */
    private DijkstraVisitedBusGraph visitedBusGraph;

    public DijkstraBusGraph(char[] busStationVertexArr, int[][] busRouteMatrixArr) {
        this.busStationVertexArr = busStationVertexArr;
        this.busRouteMatrixArr = busRouteMatrixArr;
    }

    /**
     * 显示图的邻接矩阵: 公交线路
     */
    public void showDijkstraBusGraph() {
        for (int[] busRouteArr : busRouteMatrixArr) {
            System.out.println(Arrays.toString(busRouteArr));
        }
    }

    public void dijkstra(int startVertexIndex) {
        visitedBusGraph = new DijkstraVisitedBusGraph(busStationVertexArr.length, startVertexIndex);
        update(startVertexIndex);
        for (int j = 1; j < busStationVertexArr.length; j++) {
            // 选择并返回新的访问顶点
            startVertexIndex = visitedBusGraph.updateArr();
            // 更新index顶点到周围顶点的距离和前驱顶点
            update(startVertexIndex);
        }
    }

    // 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点,
    private void update(int index) {
        int distance = 0;
        // 遍历邻接矩阵busRouteMatrixArr[index]行
        for (int j = 0; j < busRouteMatrixArr[index].length; j++) {
            // 出发顶点到index顶点的距离 + 从index顶点到j顶点距离的和
            distance = visitedBusGraph.getDistance(index) + busRouteMatrixArr[index][j];
            // 如果j顶点没有被访问过，并且distance小于出发顶点到j顶点的距离, 就需要更新
            if (!visitedBusGraph.checkVertexVisited(j) && distance < visitedBusGraph.getDistance(j)) {
                // 更新j顶点的前驱为index顶点
                visitedBusGraph.updatePreVisitedBusStationVertex(j, index);
                // 更新出发顶点到j顶点的距离
                visitedBusGraph.updateDistance(j, distance);
            }
        }
    }

    public void showDijkstra() {
        visitedBusGraph.show();
    }
}
